package wordBreak139;

import java.util.*;

public class WordBreak {

    public static void main(String[] args) {
        WordBreak wordBreak = new WordBreak();
        String s = "leetcode";

        List<String> list  = new ArrayList<>();
        list.add("leet");
        list.add("code");

        System.out.println(wordBreak.wordBreak(s, list));
    }

    Map<String, Boolean> map = new HashMap<>();
    public boolean wordBreak(String s, List<String> wordDict) {
        if(s.equals("")){
            return true;
        }
        if (map.containsKey(s)) {
            return false;
        }

        boolean res = false;
        for (int i = 0; i <s.length() ; i++) {
            if(wordDict.contains(s.substring(0,i+1))){
                res = res || wordBreak(s.substring(i+1),wordDict);
                if(!res){
                    map.put(s.substring(i + 1), true);
                }
            }

        }
        return res;
    }

}
